package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @description:
 * @author: ywk
 * @date: 2021-04-23
 */
public class 加起来和为目标值的组合 {
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();

    public static ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        if (num == null || num.length == 0 || target <= 0)
            return list;
        Arrays.sort(num);
        combinationSum2(num, target, 0, new ArrayList<>());
        return list;
    }

    private static void combinationSum2(int[] num, int target, int index,
                                        ArrayList<Integer> curList) {
        if (target == 0) {
            ArrayList<Integer> copy = new ArrayList<>(curList);
            list.add(copy);
            return;
        }
        for (int i = index; i < num.length; i++) {
            int n = num[i];
            if (target - n < 0) {
                return;
            }
            if (i > index && num[i - 1] == num[i]) {
                continue;
            } else {
                curList.add(n);
                combinationSum2(num, target - n, i + 1, curList);
                curList.remove(curList.size() - 1);
            }

        }
    }

    public static void main(String[] args) {
        System.out.println(combinationSum2(new int[]{100, 10, 20, 70, 60, 10, 50}, 80));
    }

}
